/*
Date:20210610 0:08PM
key: 二叉搜索树第k大是从后往前数，因此递归结构为 右 vis 左，vis部分引用计数一个变量，此变量+1至k就可以return。其余情况return INT_MIN。
    然后左右递归就根据return值决定这一层要不要return。
 */
class Solution {
public:
    int kthLargest1(TreeNode* root, int k,int&count) 
    {
        if(root!=NULL)
        {
            
            int r= kthLargest1(root->right, k,count);
            if(r!=INT_MIN){return r;}
            count++;
            if(k==count){return root->val;}
            int l= kthLargest1(root->left, k,count);
            if(l!=INT_MIN){return l;}
        }
        
        return INT_MIN;
    }
    int kthLargest(TreeNode* root, int k) 
    {
        int count=0;
        if(root!=NULL)
        {
            return kthLargest1(root,k,count);
            
        }else{return 0;}
    }
};

/*
Date:上面是中序遍历从后往前输出。我此处为通过检查右边比当前节点大的数字数量决定往左还是右，问题规模一次减半。
 */
class Solution {
public:
    int toatalNum(TreeNode* root)
    {
        if(root==NULL){return 0;}
        else
        {
            return 1+toatalNum(root->left)+toatalNum(root->right);
        }
    }
    int kthLargest(TreeNode* root, int k) {
        //if(root==NULL){return -1;}
        if(toatalNum(root->right)==k-1)
        {
            return root->val;
        }
        else
        {
            if(toatalNum(root->right)>k-1)
            {
                return kthLargest(root->right,k);
            }
            else
            {
                return kthLargest(root->left,k-(1+toatalNum(root->right)));
            }
        }
    }
};